This phase III randomized study is attempting to compare the effectiveness of standard single agent therapy (cisplatin) to a 2 drug combination therapy (navelbine plus cisplatin) on survival and time to disease progression in this patient population. Navelbine is an investigational drug that, in laboratory settings, has shown activity against non-small cell lung cancer. There is a great need for new and more effective therapies for metastatic non small cell lung cancer. This is a multicenter trait of SWOG.